package org.example.myleet.p1319;

import java.util.HashSet;
import java.util.Set;

public class Solution {
    /**
     * 23 ms
     * 运用并查集检查连通性以及获得不连通的图数
     */
    public int makeConnected(int n, int[][] connections) {
        if (n == 1) {
            return 0;
        }
        if (connections.length < n-1) {
            return -1;
        }
        UnionFind uf = new UnionFind(n);
        Set<Integer> nodes = new HashSet<>();
        for (int[] connection : connections) {
            nodes.add(connection[0]);
            nodes.add(connection[1]);
            uf.union(connection[0], connection[1]);
        }
        //需要操作的次数 = 独立连通图的数量 - 1
        int needOperation = uf.getGroupCount()-1;
        if (uf.redundantEdgeCount >= needOperation) {
            return needOperation;
        }
        return -1;
    }

    static class UnionFind {
        int[] parent;
        int redundantEdgeCount;

        public UnionFind(int len) {
            this.parent = new int[len];
            this.redundantEdgeCount = 0;
            for (int i=0; i<len; i++) {
                parent[i] = i;
            }
        }

        public int find(int x) {
            int p = parent[x];
            if (p != parent[p]) {
                parent[x] = find(p);
            }
            return parent[x];
        }

        public void union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX == rootY) {
                //如果这条边上的两点本来就处于同一连通图中，则此边是多余边
                ++redundantEdgeCount;
                return;
            }
            parent[rootX] = rootY;
        }

        public int getGroupCount() {
            //统计不同的root数量，即为独立的连通图数量
            Set<Integer> roots = new HashSet<>();
            for (int i=0; i<parent.length; i++) {
                int root = find(i);
                roots.add(root);
            }
            return roots.size();
        }
    }
}
